A middlebox is a network appliance that manipulates Internet traffic by optimizing data flow across the network. Middleboxes can be configured as wide area network (“WAN”) optimizers and can be deployed in pairs across two geographically separated locations to optimize data traffic between the two middleboxes. Middleboxes can be connected through a single link or multiple links such as a leased line link and a broadband link. Middleboxes such as WAN optimizers sometimes optimize internet traffic by performing computation of network traffic packets passing from local area network (“LAN”) to WAN. Bursts of sudden increases in traffic across a number of connections may result in packet processing queue build up. As a result of the limited appliance resources such as CPU capacity and available memory, the appliance may experience transmission latency in processing the packets. Consequently, users sending and receiving Internet traffic across the middlebox appliance could experience poor quality of service resulting from the resource crunch.